#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include "Stack.h"

void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

int GreatMid(int* a, int left, int right)
{
	assert(a);
	int mid = (left + right)/2;
	if (a[left] > a[mid])
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[right] > a[left])
		{
			return left;
		}
		else
		{
			return right;
		}
	}

	else   //a[left]<a[mid]
	{
		if (a[right]>a[mid])
		{
			return mid;
		}
		else if (a[right] < a[left])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	return mid;
}

int PartSort3(int* a,int begin,int end)
{
	assert(a);

	int left = begin;
	int right = end;

	int keyi = GreatMid(a,left,right);
	if (keyi != left)
	{
		Swap(&a[keyi], &a[left]);
	}
	keyi = left;

	int pre = left;
	int cur = pre + 1;

	while (cur <= right)
	{
		while (cur <= right && a[cur] >= a[keyi])
		{
			cur++;
		}
		if (cur <= right)
		{
			Swap(&a[++pre], &a[cur++]);
		}
	}
	Swap(&a[pre], &a[keyi]);
	keyi = pre;

	return keyi;
}

int PartSort2(int* a, int begin, int end)
{
	assert(a);

	int left = begin;
	int right = end;

	int keyi = GreatMid(a, left, right);
	if (keyi != left)
	{
		Swap(&a[keyi], &a[left]);
	}
	keyi = left;
   
	int key = a[keyi];
	int hole = left;

	while (left < right)
	{
		while (left < right && a[right] >= key)
		{
			right--;
		}
		a[hole] = a[right];
		hole = right;

		while (left < right && a[left] <= key)
		{
			left++;
		}
		a[hole] = a[left];
		hole = left;
	}
	a[hole] = key;
	keyi = hole;

	return keyi;
}

int PartSort1(int* a, int begin, int end)
{
	assert(a);

	int left = begin;
	int right = end;

	int keyi = GreatMid(a, left, right);
	if (keyi != left)
	{
		Swap(&a[keyi], &a[left]);
	}
	keyi = left;

	while (left < right)
	{
		while (left < right && a[right] >= a[keyi])
			right--;

		while (left < right && a[left] <= a[keyi])
			left++;

		Swap(&a[right], &a[left]);
	}
	Swap(&a[keyi], &a[left]);

	keyi = left;

	return keyi;
}

void MyPrintf(int* a, int n)
{
	assert(a);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}


void QuickSort(int* a, int begin, int end)
{
	assert(a);

	if (begin >= end)
	{
		return;
	}
	int keyi = PartSort1(a, begin, end);
	
	QuickSort(a, begin, keyi);
	QuickSort(a, keyi + 1, end);
}

void QuickSortNonR(int* a, int left, int right)
{
	assert(a);
	ST s;
	STInit(&s);
	if (left < right)
	{
		STPush(&s, right);
		STPush(&s, left);
	}

	while(!STEmpty(&s))
	{
		int begin = STTop(&s);
		STPop(&s);

		int end = STTop(&s);
		STPop(&s);

		int keyi = PartSort3(a, begin, end);

		if (keyi + 1 < end)
		{
			STPush(&s, end);
			STPush(&s, keyi);
		}

		if (begin < keyi)
		{
			STPush(&s, keyi);
			STPush(&s, begin);
		}

	}
}

int main()
{
	int a[] = { 11,42,61,928,-303,-4,-6,7,-9,44 ,-54};
	//QuickSort(a, 0, sizeof(a) / sizeof(int)-1);

	QuickSortNonR(a, 0, sizeof(a) / sizeof(int)-1);

	MyPrintf(a, sizeof(a) / sizeof(int));
	return 0;
}

